This invention relates to data bus time slot assignment, and in particular, to packing of assigned data bus time slots.
Computer and communication devices have packet handler data buses (PHDBs). The PHDBs allow individual time slots or groups of time slots to be dynamically assigned and released as required. As time slots are assigned and released, the PHDB has non-contiguous free time slots (commonly called xe2x80x9cholesxe2x80x9d) interspersed between assigned time slots. Thus, a port assignment request requiring a plurality of contiguous time slots may not be serviced because of multiple xe2x80x9cholesxe2x80x9d of unassigned time slots interspersed between the assigned time slots.
In FIG. 1, an illustration of a thirty-two time slot data bus 100 as known in the art is shown. The time slots are assigned identifiers with time slot zero 102 being first (least significant time slot) and time slot thirty-one 104 being last (most significant time slot). A time slot in the data bus is defined as the smallest switchable data unit on a data bus. Multiple contiguous time slots can be grouped together allowing higher data bandwidths to be transferred across the data bus.
Turning to FIG. 2, an illustration of a data fan-out device 202 with multiple packet interface data buses (DFMP) is shown. The fan-out device has access to multiple data buses 204-210 via one of sixteen packet handlers 212-218. The digital fan-out 202 is coupled electronically to the sixteen data buses 204-210. A data bus time slot must pair with a nibble bus time slot in order to be utilized in the DFMP embodiment. However, there are only 8 nibble bus time slots available for 16 data bus time slots at each column. In an alternate embodiment a data fan-out type 11 device is coupled to multiple data buses and does not require nibble bus time slot pairings as in the DFMP embodiment.
To accommodate the contraints from the nibble bus an optimal assignment of time slots on an even data bus 204 has the lowest time slots assigned (shown as 1) and the upper timeslots unassigned (shown as 0). The odd data bus 206 has the opposite time slot assignments. The lowest time slots are unassigned while the upper time slots are assigned. This even/odd data bus pattern is then repeated for all the other data buses.
Thus, a method and apparatus is needed to pack assigned time slots on a data bus enabling larger blocks of unassigned contiguous time slots to be available for assignment. Additionally, a method and apparatus is also needed to efficiently pack time slots in desirable portions of the DFMP data bus implementation.
In a system with one or more data buses with each data bus having a plurality of time slots, some of the time slots are assigned and carrying data while other time slots are unassigned. The unassigned time slots are assigned either individually or in groups when additional bandwidth is required. Over time the data buses have unassigned time slots xe2x80x9cholesxe2x80x9d interspersed with assigned time slots. In an individual data bus embodiment, depending on whether the designation of the data bus is odd or even, packing occurs towards the most significant time slot or the least significant time slot. In an alternate individual data bus embodiment, the data bus is divided into two sets and assigned time slots from the set with fewer assigned time slots are moved or plugged into free time slots in the other set. If the other set of time slots does not have an exactly equal number of contiguous time slots for a port having multiple time slot to be moved or plugged into, then the assigned time slots that follow an unassigned time slot are shifted in that set of time slots. The shifting of time slots results in larger grouping of contiguous time slots in the other set of time slots. In a multi-data bus embodiment, the moving and shifting of time slots occurs between data buses in addition to within one of the data buses.